//FFFFFFFFFF    X      X    BBBBBBBBBBB
//FFFFFFFFFF     X    X     BBBBBBBBBBB
//FF              X  X      BB       BB
//FFFFFFFFFF       XX       BBBBBBBBBBB
//FFFFFFFFFF       XX       BBBBBBBBBBB
//FF              X  X      BB       BB
//FF             X    X     BBBBBBBBBBB
//FF            X      X    BBBBBBBBBBB
#include<bits/stdc++.h>
#include<conio.h>
//#define int long long
#define psp putchar(' ')
#define endl putchar('\n')
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(char v:s)putchar(v);
}
int n=5,m,k;
int T;
char c[M][M];
int vis[M][M];
struct node{
	int x,y,dis;
};
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int bfs(int X,int Y){
	memset(vis,0,sizeof(vis));
	vis[X][Y]=1;
	queue<node>q;
	q.push(node{X,Y,0});
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,w=q.front().dis;
		q.pop();
		if(c[x][y]=='P')return w;
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx<1||yy<1||xx>n||yy>n||vis[xx][yy]||c[xx][yy]=='#')continue;
			vis[xx][yy]=1;
			q.push(node{xx,yy,w+1});
		}
	}
	return 0;
}
signed main(){
	//ios::sync_with_stdio(0);
	srand(time(0));
	while(1){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				c[i][j]='.';
			}
		}
		int x=(rand()-1)%n+1;
		int y=(rand()-1)%n+1;
		for(int i=1;i<=(n/3)*n;i++){
			while(c[x][y]!='.'){
				x=(rand()-1)%n+1;
				y=(rand()-1)%n+1;
			}
			c[x][y]='#';
		}
		while(c[x][y]!='.'){
			x=(rand()-1)%n+1;
			y=(rand()-1)%n+1;
		}
		c[x][y]='P';
		while(c[x][y]!='.'){
			x=(rand()-1)%n+1;
			y=(rand()-1)%n+1;
		}
		int kkk=bfs(x,y);
		int cnt=0;
		while(kkk>=(n/5)*n){
			system("cls");
			cout<<n<<'x'<<n<<'\n';
			cout<<"best steps: "<<kkk<<"  Your steps: "<<cnt<<'\n';
			if(c[x][y]=='P')break;
			c[x][y]='O';
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					cout<<c[i][j];
				}
				cout<<'\n';
			}
			char op=getch();
			if(op=='w'&&x-1>0&&c[x-1][y]!='#'){
				c[x][y]='.';
				x--;
				cnt++;
			}
			if(op=='a'&&y-1>0&&c[x][y-1]!='#'){
				c[x][y]='.';
				y--;
				cnt++;
			}
			if(op=='s'&&x+1<=n&&c[x+1][y]!='#'){
				c[x][y]='.';
				x++;
				cnt++;
			}
			if(op=='d'&&y+1<=n&&c[x][y+1]!='#'){
				c[x][y]='.';
				y++;
				cnt++;
			}
		}
		if(kkk>=(n/5)*n)system("pause");
		n+=(kkk>=(n/5)*n);
	}
}
